package com.major.linkedlist.josephus;

public class CircleSingleLink {
    // 创建一个节点，没有编号
    private Boy first = null;

    // 构建出链表
    public void addBoys(int nums){
        // 数据校验
        if (nums < 1){
            System.out.println("人数不正确");
            return;
        }

        // 构建
        Boy curBoy = null;      // 辅助
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1){
                first = boy;
                boy.setNext(boy);   // 闭环
                curBoy = first;     // curBoy一直指向最后一个
            } else {
                boy.setNext(first); // 向后跟第一个闭环
                curBoy.setNext(boy);// 向前跟前一个闭环
                curBoy = boy;       // curBoy一直指向最后一个

            }

        }


    }

    // 遍历
    public void showBoys() {
        if (first == null) {    // 为空
            System.out.println("没有添加boy，构成链表");
            return;
        }

        Boy temp = first;
        while (true) {
            System.out.println(temp.getNo());
            if (temp.getNext() == first) {      // 遍历完毕
                break;
            }
            temp = temp.getNext();
        }
    }


    /**
     * 出圈
     * @param startNo 从第几个开始
     * @param countNum 每次数几个
     * @param nums 开始有几个
     */
    public void countOut(int startNo, int countNum, int nums){
        // 数据校验
        if (startNo < 1 || first == null || startNo > nums){
            System.out.println("参数有误");
            return;
        }
        // 辅助变量helper，指向first前一位
        Boy helper = first;
        while (helper.getNext() != first) {     // 指向first前一位，因为单向链表不能删除当前节点
            helper = helper.getNext();          // 需要借助前一个结点helper来删除当前结点，即first
        }

        // 报数前，将first和helper移动到startNo：移动startNo-1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        while (helper != first) { // 只有一个结点退出循环
            // 报数时，移动nums-1次
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            // 删除 first指向的boy
            System.out.println(first.getNo());
            first = first.getNext();                //first前移得到新的first
            helper.setNext(first);        //helper指向新的first
        }
        System.out.println("剩下一个："+ first.getNo());
    }
}
